The present invention relates to the field of compression and decompression systems; more particularly, the present invention relates to lossless discrete cosine transform (DCT)-based compression which is reversible.
The Discrete Cosine Transform (DCT) is an irrational transform commonly used in lossy image compression. The DCT is commonly used in lossy image compression. It is used in many modes of the JPEG at standard and the MPEG standards and future HDTV in the United States. For a discussion on the various standards, see ISO Standard documents ISO/IEC 10918 JPEG), 11172 (MPEG 1), 13818 (MPEG 2) and William B. Pennebaker and Joan L. Mitchell, xe2x80x9cJPEG Still Image Data Compression Standard,xe2x80x9d 1993. The basis vectors of DCT have irrational values. Theoretically, integer inputs result in irrational transform coefficients. Therefore, infinite precision is required to perform those transforms exactly. For use in compression, transform coefficients must be rounded to a finite representation.
With most transform implementations, the rounding coefficients to integers does not guarantee that every unique integer input results in a different output. Therefore, the inverse DCT cannot reconstruct the input exactly. The error due to forward and inverse DCT transforms without quantization is referred to as systemic error. This systemic error prevents DCT implementations from being used in lossless compression without retaining a difference or error image.
In practical DCT implementations, the transform basis vectors are also rounded. The difference between a given implementation and the ideal transform (or a high accuracy floating point implementation) is referred to as mismatch. Low mismatch is required for data interchange. There can be a trade-off between the amount of mismatch and speed, cost and other desirable features.
A parameterized transform referred to herein as the Allen Parameterized Transform (APT) is a family of fast transforms which can implement the DCT or rational transforms that are arbitrarily close to the DCT. The APT is also referred to as a generalized Chen transform (GCT) For more information on the APT, see J. Allen, xe2x80x9cGeneralized Chen Transform: A Fast Transform for Image Compression,xe2x80x9d Journal of Electronic Imaging, Vol. 3(4), October 1994, pgs. 341-347; J. Allen, xe2x80x9cAn Approach to Fast Transform Coding in Software,xe2x80x9d Signal Processing: Image Communication. Vol. 8, pp. 3-11, 1996; and U.S. Pat. No. 5,129,015.
The present invention provides a reversible block based transform, such as, for example, a reversible DCT. The DCT of the present invention may be included in a DCT-based compressor/decompressor that may be used in a lossless compression/decompression system. The present invention also provides DCT transforms with no systemic error and no (or low) mismatch.
A reversible Discrete Cosine Transform (DCT) is described. The reversible DCT may be part of a compressor in a system. The system may include a decompressor with a reversible inverse DCT for lossless decompression or a legacy decompressor with an inverse DCT for lossy decompression.
In one embodiment, the compressor comprises a DCT compressor having a multiple rotations (e.g., 2 point (2xc3x972) integer rotations), a 4 point parameterized transform, and a subsidiary matrix. The 4 point transform comprises a rotation by B, while the subsidiary matrix comprises a rotation by A and a rotation by C.
The present invention also provides a method for creating a look up table for rounding offsets for use in a reversible DCT.